/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package ads.sort;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

/**
 *
 * @author framet-lap
 */
public class SortMagic {

    public static int[] quickSortPivotFirst(int[] array, int lower, int upper) {
//        try {
        int pivot = lower;
        int pivotValue = array[pivot];
        int swappi = lower;//swappi der freundliche swapindex
        swap(array, pivot, upper);
        for (int i = lower; i < upper; i++) {
            if (array[i] <= pivotValue) {
                swap(array, i, swappi);
                swappi++;
            }
        }
        swap(array, upper, swappi);
        if ((swappi - lower) > 1) {
            quickSortPivotFirst(array, lower, swappi - 1);
        }
        if ((upper - swappi) > 1) {
            quickSortPivotFirst(array, swappi + 1, upper);
        }
//        } catch (StackOverflowError ex) {
//            System.out.println(" lol ");
//        }
        return array;
    }

    public static int[] quickSortPivotLast(int[] array, int lower, int upper) {
        int pivot = upper;
        int pivotValue = array[pivot];
        int swappi = lower;//swappi der freundliche swapindex
        swap(array, pivot, upper);
        for (int i = lower; i < upper; i++) {
            if (array[i] <= pivotValue) {
                swap(array, i, swappi);
                swappi++;
            }
        }
        swap(array, upper, swappi);
        if ((swappi - lower) > 1) {
            quickSortPivotFirst(array, lower, swappi - 1);
        }
        if ((upper - swappi) > 1) {
            quickSortPivotFirst(array, swappi + 1, upper);
        }
        return array;
    }

    public static int[] insertionSort(int[] array) {
        int temp, j;
        for (int i = 1; i < array.length; i++) {
            temp = array[i];
            j = i - 1;

            while (j >= 0 && array[j] > temp) {
                array[j + 1] = array[j];
                j--;
            }

            array[j + 1] = temp;
        }
        return array;
    }

    public static int[] quickSortPivotMedian(int[] array, int lower, int upper, int medianElementCount, int threshold) {
        if (array.length <= threshold) {
            return insertionSort(array);
        } else {

            int pivot = calculateMedian(array, medianElementCount);

            int pivotValue = array[pivot];
            int swappi = lower;//swappi der freundliche swapindex
            swap(array, pivot, upper);
            for (int i = lower; i < upper; i++) {
                if (array[i] <= pivotValue) {
                    swap(array, i, swappi);
                    swappi++;
                }
            }
            swap(array, upper, swappi);
            if ((swappi - lower) > 1) {
                quickSortPivotFirst(array, lower, swappi - 1);
            }
            if ((upper - swappi) > 1) {
                quickSortPivotFirst(array, swappi + 1, upper);
            }
            return array;
        }
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static int[] createUnsortedArray(int size) {
        Random random = new Random();
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size * 1000);
        }
        return array;
    }

    private static int calculateMedian(int[] array, int elementCount) {
        if (elementCount > array.length) {
            elementCount = array.length;
        }
        int[] medianovic = new int[elementCount];
        HashMap<Integer, Integer> hashmaplana = new HashMap<>();
        for (int i = 0; i < elementCount; i++) {
            medianovic[i] = array[(array.length / elementCount) * i];
            hashmaplana.put(medianovic[i], (array.length / elementCount) * i);
        }
        Arrays.sort(medianovic);
        return hashmaplana.get(medianovic[medianovic.length / 2]);
    }
}
